#include <iostream>
#include <vector>

namespace me
{
    template <typename T>
    class heap
    {
    public:
        heap():_size(0) {}

        void push(const T& data)
        {
            // 将元素插入到完全二叉树从左到右的最后一个叶子节点处
            _heap.emplace_back(data);
            _size++;
            
            // 向上调整
            adjustUp(size - 1); // 对插入的元素进行向上调整，使之依旧是一个堆
        }

        void pop()
        {
            // 堆的pop删除堆顶的数据，将堆顶的数据与最后一个叶子节点进行交换
            // 然后从堆顶开始向下调整，使之依旧为堆
            std::swap(_heap[0], _heap[_size - 1]);
            _heap.pop_back();
            _size--; // 删除，让size向前移动即可

            adjustDown(0);
        }

        T top() const
        {
            if(_size) return _heap[0];
        }


        size_t size() const { return _size; }
        bool empty() const { return _size == 0; }
    private:
        void adjustUp(size_t child) // 默认是大堆
        {
            // 记录插入的元素
            T val = _heap[child]; 

            while(child > 0) {
                size_t parent = (child - 1) / 2;
                if(_heap[parent] >= val) break; // 满足大堆要求，不需要向上调整

                // 不满足，则交换，父节点下移
                _heap[child] = _heap[parent];

                // 更新child，继续向上调整
                child = parent;
            }

            // 跳出循环，此时child的位置，就是插入元素val调整后的位置
            _heap[child] = val;
        }

        void adjustDown(size_t parent) // 默认是大堆
        {
            // 从根开始向下调整，如果根大于左右孩子，退出
            // 如果根小于其中某一个，则交换
            // 如果根小于两者，则与更大的交换

            T val = _heap[parent];
            int child = parent * 2 + 1; // 默认大的是左孩子

            while(child < _size/*确保有孩子进入循环，没有孩子说明此时已经调整到最后一层了*/) {
                if(child + 1 < _size && _heap[child] < _heap[child + 1]) {
                    child += 1;
                }

                if(val >= _heap[child]) break;
                _heap[parent] = _heap[child];
                parent = child;
                child = parent * 2 + 1;
            }
            _heap[parent] = val; // 此时parent的位置就是最终调整好的位置
        }
    private:
        std::vector<T> _heap;
        size_t _size;
    };
}

// 大堆
void adjustDown(std::vector<int> &arr, int parent, int size)
{
    int val = arr[parent];

    int child = parent*2 + 1;// 左孩子
    while(child < size) {
        // 假设法求出最大的孩子
        if(child + 1 < size && arr[child] < arr[child+1]) {
            child += 1;
        }

        // 向下调整
        if(val >= arr[child]) break;
        // 将孩子上移
        arr[parent] = arr[child];
        parent = child;
        child = parent * 2 + 1;
    }
    arr[parent] = val;
}

void heapSort(std::vector<int> &arr) // 升序
{
    // 1.在已有数组的基础上，进行向下调整建堆，从第一个非叶子节点开始
    int size = arr.size();
    for(int i = (size - 1 - 1) / 2; i >= 0; i--) {
        adjustDown(arr, i, size);
    }

    // 2.以此将堆顶数据进行交换
    int end = arr.size() - 1;
    while(end) {
        std::swap(arr[0], arr[end]);
        adjustDown(arr, 0, end);
        end--;
    }
}

// 小堆
void adjustDown(std::vector<int> &arr, int parent, int size)
{
    int val = arr[parent];

    int child = parent*2 + 1;// 左孩子
    while(child < size) {
        // 假设法求出最小的孩子
        if(child + 1 < size && arr[child] > arr[child+1]) {
            child += 1;
        }

        // 向下调整
        if(val <= arr[child]) break;
        // 将孩子上移
        arr[parent] = arr[child];
        parent = child;
        child = parent * 2 + 1;
    }
    arr[parent] = val;
}

std::vector<int> topK(std::vector<int> &arr, int k)
{
    // 1.取出前k个元素建立一个小堆——建堆使用向下调整建堆
    std::vector<int> heap(arr.begin(), arr.begin() + k);
    for(int i=(k-2)/ 2; i>=0; i--) {
        adjustDown(heap, i, k);
    }

    // 2.遍历剩余元素，与堆顶元素进行比较，如果大于堆顶元素，则交换，并向下调整
    for(int i = k; i<arr.size(); i++) {
        if(arr[i] > heap[0]) {
            heap[0] = arr[i];
            adjustDown(heap, 0, k);
        }
    }
    return heap;
}
    
int main()
{
    return 0;
}